package jzOffer;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Num38 {
    List<String> list=new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c=s.toCharArray();
        dfs(0);
        return list.toArray(new String[list.size()]);
    }
    private void dfs(int x){
        if(x==c.length-1) {
            list.add(String.valueOf(c));
            return;
        }
        Set<Character> set=new HashSet<>();
        for(int i=x;i<c.length;i++){
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i,x);
            dfs(x+1);
            swap(i,x);
        }
    }
    private void swap(int i,int j){
        char tmp=c[i];
        c[i]=c[j];
        c[j]=tmp;
    }
}
